{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #最长公共子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestCommonSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长公共子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个字符串&nbsp;<code>text1</code> 和&nbsp;<code>text2</code>，返回这两个字符串的最长 <strong>公共子序列</strong> 的长度。如果不存在 <strong>公共子序列</strong> ，返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>一个字符串的&nbsp;<strong>子序列</strong><em>&nbsp;</em>是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>&quot;ace&quot;</code> 是 <code>&quot;abcde&quot;</code> 的子序列，但 <code>&quot;aec&quot;</code> 不是 <code>&quot;abcde&quot;</code> 的子序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>两个字符串的 <strong>公共子序列</strong> 是这两个字符串所共同拥有的子序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>text1 = &quot;abcde&quot;, text2 = &quot;ace&quot; \n",
    "<strong>输出：</strong>3  \n",
    "<strong>解释：</strong>最长公共子序列是 &quot;ace&quot; ，它的长度为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>text1 = &quot;abc&quot;, text2 = &quot;abc&quot;\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>最长公共子序列是 &quot;abc&quot; ，它的长度为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>text1 = &quot;abc&quot;, text2 = &quot;def&quot;\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>两个字符串没有公共子序列，返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= text1.length, text2.length &lt;= 1000</code></li>\n",
    "\t<li><code>text1</code> 和&nbsp;<code>text2</code> 仅由小写英文字符组成。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 1143&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/longest-common-subsequence/\">https://leetcode-cn.com/problems/longest-common-subsequence/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [qJnOS7](https://leetcode.cn/problems/qJnOS7/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [qJnOS7](https://leetcode.cn/problems/qJnOS7/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abcde\"\\n\"ace\"', '\"abc\"\\n\"abc\"', '\"abc\"\\n\"def\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        #dp[i][j]表示text1到i和text2到j的最长公共子序列\n",
    "        #这个概念不好理解，但是却容易构造状态方程\n",
    "        m, n = len(text1), len(text2)\n",
    "        dp = [0]*(n+1)\n",
    "        #空间优化 只需要记录左上角元素\n",
    "        for i in range(1,m+1):\n",
    "            temp = 0\n",
    "            for j in range(1,n+1):\n",
    "                # temp = dp[j-1]\n",
    "                pre = dp[j]\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[j] = temp+1\n",
    "                else:\n",
    "                    dp[j] = max(dp[j],dp[j-1])\n",
    "                temp = pre\n",
    "                # temp = pre\n",
    "                # pre = dp[j]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        my_mat=[[0]*(len(text1)+1) for i in range(len(text2)+1)]\n",
    "        for i in range(1,len(text2)+1):\n",
    "            for j in range(1,len(text1)+1):\n",
    "                if text2[i-1]==text1[j-1]:\n",
    "                    my_mat[i][j]=my_mat[i-1][j-1]+1\n",
    "                else:\n",
    "                    my_mat[i][j]=max(my_mat[i-1][j],my_mat[i][j-1])\n",
    "        return max(max(my_mat[i]) for i in range(len(text2)+1))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        m, n = len(text1), len(text2)\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if text1[i] == text2[j]:\n",
    "                    dp[i+1][j+1] = dp[i][j] + 1\n",
    "                else:\n",
    "                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])\n",
    "        return dp[m][n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        l1 = len(text1)\n",
    "        l2 = len(text2)\n",
    "\n",
    "        # Create a memoization table\n",
    "        memo = [[-1] * l2 for _ in range(l1)]\n",
    "\n",
    "        def dfs(i, j):\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "\n",
    "            if memo[i][j] != -1:\n",
    "                return memo[i][j]\n",
    "\n",
    "            if text1[i] == text2[j]:\n",
    "                result = dfs(i - 1, j - 1) + 1\n",
    "            else:\n",
    "                result = max(dfs(i - 1, j), dfs(i, j - 1))\n",
    "\n",
    "            memo[i][j] = result\n",
    "            return result\n",
    "\n",
    "        return dfs(l1 - 1, l2 - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def process2(self, x, y, r, i, j):\n",
    "        if r[i][j] != -1:\n",
    "            return r[i][j]\n",
    "\n",
    "        if i == 0 and j == 0:\n",
    "            if x[0] == y[0]:\n",
    "                r[0][0] = 1\n",
    "                return 1\n",
    "            else:\n",
    "                r[0][0] = 0\n",
    "                return 0\n",
    "        elif i == 0:\n",
    "            if x[i] == y[j]:\n",
    "                r[0][j] = 1\n",
    "                return 1\n",
    "            else:\n",
    "                q = self.process2(x, y, r, i, j - 1)\n",
    "                r[0][j] = q\n",
    "                return q\n",
    "        elif j == 0:\n",
    "            if x[i] == y[j]:\n",
    "                r[i][0] = 1\n",
    "                return 1\n",
    "            else:\n",
    "                q = self.process2(x, y, r, i - 1, j)\n",
    "                r[i][0] = q\n",
    "                return q\n",
    "        else:\n",
    "            p1, p2, p3 = 0, 0, 0\n",
    "            if x[i] != y[j]:\n",
    "                p1 = self.process2(x, y, r, i, j - 1)\n",
    "                p2 = self.process2(x, y, r, i - 1, j)\n",
    "            else:\n",
    "                p3 = self.process2(x, y, r, i - 1, j - 1) + 1\n",
    "            q = max(p3, max(p1, p2))\n",
    "            r[i][j] = q\n",
    "            return q\n",
    "\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        if(text1 == '' or text2 == '' or len(text1) == 0 or len(text2) == 0):\n",
    "            return 0\n",
    "\n",
    "        r = [[-1 for i in range(len(text2))] for j in range(len(text1))]\n",
    "        i = len(text1) - 1\n",
    "        j = len(text2) - 1\n",
    "        length = self.process2(text1, text2, r, i, j)\n",
    "        return length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        text1 = \" \" + text1\n",
    "        text2 = \" \" + text2\n",
    "        m = len(text1)\n",
    "        n = len(text2)\n",
    "        arr = [[0] * n for i in range(m)]\n",
    "        print(arr)\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                if(text1[i] == text2[j]):\n",
    "                    arr[i][j] = arr[i-1][j-1] + 1\n",
    "                else:\n",
    "                    arr[i][j] = max(arr[i-1][j],arr[i][j-1])\n",
    "        return arr[m-1][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        m, n = len(text1), len(text2)\n",
    "\n",
    "        # 初始化\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        print(dp)\n",
    "        # 状态更新\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        \n",
    "        return dp[m][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, arr1: str, arr2: str) -> int:\n",
    "        m, n = len(arr1), len(arr2) \n",
    "        dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "        g = [[-1] * (n+1) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if arr1[i-1] == arr2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1 \n",
    "                    g[i][j] = arr1[i-1] \n",
    "                else:\n",
    "                    if dp[i-1][j] > dp[i][j-1]:\n",
    "                        dp[i][j] = dp[i-1][j]\n",
    "                        g[i][j] = g[i-1][j]\n",
    "                    elif dp[i-1][j] < dp[i][j-1]:\n",
    "                        dp[i][j] = dp[i][j-1]\n",
    "                        g[i][j] = g[i][j-1]\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i-1][j] \n",
    "                        if g[i-1][j] <= g[i][j-1]:\n",
    "                            g[i][j] = g[i-1][j]\n",
    "                        else:\n",
    "                            g[i][j] = g[i][j-1] \n",
    "\n",
    "        return dp[m][n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        m = len(text1)\n",
    "        n = len(text2)\n",
    "        dp = [[0 for j in range(n+1)] for i in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                    print(text1[i-1], text2[j-1])\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])\n",
    "        max_len = dp[-1][-1]\n",
    "        print(dp)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        m, n = len(text1), len(text2)\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        \n",
    "        for i in range(m+1):\n",
    "            dp[i][0] = 0\n",
    "        for j in range(n+1):\n",
    "            dp[0][j] = 0\n",
    "\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                flag = text1[i-1]==text2[j-1]\n",
    "                dp[i][j] = max(dp[i-1][j-1]+flag,dp[i-1][j],dp[i][j-1])\n",
    "        print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dp =[[0]*(len(text1)+1) for _ in range(len(text2)+1)]\n",
    "        print(dp)\n",
    "        for i in range(1,len(text2)+1):\n",
    "            for j in range(1,len(text1)+1):\n",
    "                if text2[i-1]==text1[j-1]:\n",
    "                    dp[i][j] =dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n",
    "        print(dp)\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        #LCS 虽然跟求子串那个kmp差不多，但是这个只能做到omn。（这个是最长子序列，不是最长子串）\n",
    "        #见718最长重复子数组，28kmp\n",
    "        m1 = len(text1)\n",
    "        m2 = len(text2)\n",
    "        dp = [[0]*(m2+1) for _ in range(m1+1)]\n",
    "        res = [[\"\"]*(m2+1) for _ in range(m1+1)]\n",
    "        for i in range(1,m1+1):\n",
    "            for j in range(1,m2+1):\n",
    "                if text1[i-1]==text2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]+1\n",
    "                    res[i][j] = res[i-1][j-1]+text1[i-1]\n",
    "                else:\n",
    "                    if dp[i-1][j]>dp[i][j-1]:\n",
    "                        dp[i][j] = dp[i-1][j]\n",
    "                        res[i][j] = res[i-1][j]\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i][j-1]\n",
    "                        res[i][j] = res[i][j-1]\n",
    "        \n",
    "        # print(res[-1][-1]) #这样应该就能找到这个lcs了\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        m=len(text1)\n",
    "        n=len(text2)\n",
    "        dp=[[0]*(m+1) for _ in range(n+1)]          #m列 n行\n",
    "        #print(np.array(dp).shape)\n",
    "        for i in range(1,n+1):           #第i~n~str2行，第j~m~str1列\n",
    "            for j in range(1,m+1):\n",
    "                if text2[i-1]==text1[j-1]:\n",
    "                    dp[i][j]=dp[i-1][j-1]+1\n",
    "                else:\n",
    "                    #print(i-1,j-1)\n",
    "                    dp[i][j]=max(dp[i][j-1],dp[i-1][j])\n",
    "        \n",
    "        return dp[n][m]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        '''\n",
    "        这道题依稀记得转移方程:\n",
    "        对于字符串a,b，设dp[n][m]表示以从第n个字符开始的a与第m个字符开始的b 之间的最长子序列。那么：\n",
    "        dp[n][m]= dp[n+1][m+1] +1 如果首字母相同\n",
    "        dp[n][m]=max(dp[n+1][m], dp[n][m+1]) 如果首字母不相同\n",
    "\n",
    "        '''\n",
    "        self.a=text1\n",
    "        self.b=text2\n",
    "        # self.dp= np.ones([len(text1),len(text2)],dtype=np.int32)*-1\n",
    "        self.dp= [[-1 for j in range(len(text2))] for i in range(len(text1))]\n",
    "\n",
    "        \n",
    "        return self.f(0,0)\n",
    "        \n",
    "    def f(self,n,m):\n",
    "        if  n>=len(self.a) or m>=len(self.b):\n",
    "            return 0\n",
    "\n",
    "        if self.dp[n][m] != -1:\n",
    "            return self.dp[n][m]\n",
    "        if self.a[n]==self.b[m]:\n",
    "            self.dp[n][m]=1+self.f(n+1,m+1)\n",
    "        else:\n",
    "            self.dp[n][m]=max(self.f(n+1,m),self.f(n,m+1))\n",
    "        return self.dp[n][m]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        len1 = len(text1)\n",
    "        len2 = len(text2)\n",
    "        dp = np.zeros([len1+1, len2+1]).astype(int)\n",
    "        dp = [[0]*(len2+1) for _ in range(len1+1)]\n",
    "        for i in range(1,len1+1):\n",
    "            for j in range(1,len2+1):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])\n",
    "        return int(dp[-1][-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        m, n = len(text1), len(text2)\n",
    "        dp = [[0] * (n+1) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(m):\n",
    "            dp[i+1][0] = i+1\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[0][i+1] = i+1\n",
    "\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1)\n",
    "\n",
    "        # print(dp)\n",
    "\n",
    "        ans = (m+n-dp[-1][-1]) // 2\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        n = len(text1)\n",
    "        m = len(text2)\n",
    "        table = [[] for _ in range(n + 1)]\n",
    "        for i in range(n+1):\n",
    "            table[i] = [0 for _ in range(m + 1)]\n",
    "            table[i][0] = i\n",
    "        for j in range(m+1):\n",
    "            table[0][j] = j\n",
    "        \n",
    "        # 求只有删除操作的最小编辑距离\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    table[i][j] = table[i-1][j-1]\n",
    "                else:\n",
    "                    table[i][j] = min(table[i-1][j], table[i][j-1]) + 1\n",
    "        return int((len(text1) + len(text2) - table[n][m]) / 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        n1 = len(text1) + 1\n",
    "        n2 = len(text2) + 1\n",
    "        dp = [[ 0 if i==0 or j==0 else float('-inf') for i in range(n2)] for j in range(n1)]\n",
    "        for i in range(1, n1):\n",
    "            for j in range(1, n2):\n",
    "                if text1[i - 1] == text2[j - 1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])\n",
    "        return dp[n1-1][n2-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        n1,n2 = len(text1),len(text2)\n",
    "        dp = np.zeros([n1,n2]).tolist()\n",
    "        for i in range(n1):\n",
    "            for j in range(n2):\n",
    "                if i==0:dp[i][j]=1 if text1[i] in text2[:j+1] else 0\n",
    "                elif j==0:dp[i][j]=1 if text2[j] in text1[:i+1] else 0\n",
    "                else:\n",
    "                    if text1[i]==text2[j]:dp[i][j] = dp[i-1][j-1]+1\n",
    "                    else:dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dic = dict()\n",
    "        dic[0] = {}\n",
    "        dic[0][0] = 1 if text1[0] == text2[0] else 0\n",
    "        for i in range(len(text1) - 1):\n",
    "            dic[i + 1] = {}\n",
    "            dic[i + 1][0] = 1 if text1[i + 1] == text2[0] else max(dic[i][0], 0)\n",
    "        for i in range(len(text2) - 1):\n",
    "            dic[0][i + 1] = 1 if text1[0] == text2[i + 1] else max(dic[0][i], 0)\n",
    "        for i in range(len(text1)):\n",
    "            for j in range(len(text2)):\n",
    "                if i == 0 or j == 0:\n",
    "                    continue\n",
    "                if text1[i] == text2[j]:\n",
    "                    dic[i][j] = dic[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dic[i][j] = max(dic[i - 1][j], dic[i][j - 1])\n",
    "        return dic[i][j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dic = dict()\n",
    "        dic[0] = {}\n",
    "        dic[0][0] = 1 if text1[0] == text2[0] else 0\n",
    "        for i in range(len(text1) - 1):\n",
    "            dic[i + 1] = {}\n",
    "            dic[i + 1][0] = 1 if text1[i + 1] == text2[0] else max(dic[i][0], 0)\n",
    "        for i in range(len(text2) - 1):\n",
    "            dic[0][i + 1] = 1 if text1[0] == text2[i + 1] else max(dic[0][i], 0)\n",
    "        for i in range(len(text1)):\n",
    "            for j in range(len(text2)):\n",
    "                if i == 0 or j == 0:\n",
    "                    continue\n",
    "                if text1[i] == text2[j]:\n",
    "                    dic[i][j] = dic[i - 1][j - 1] + 1\n",
    "                else:\n",
    "                    dic[i][j] = max(dic[i - 1][j], dic[i][j - 1])\n",
    "        return dic[i][j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        \n",
    "        dp = []#. dp[i][j]  表示text1[0:i+1] 和text2[0:j+1] 直接的最长公共子序列\n",
    "        for i in range(len(text1)):\n",
    "            dp.append([])\n",
    "            for j in range(len(text2)):\n",
    "                dp[i].append([])\n",
    "\n",
    "        data1 = defaultdict(list)\n",
    "        data2 = defaultdict(list)\n",
    "        for i, c in enumerate(text1):\n",
    "            data1[c].append(i)\n",
    "            \n",
    "        for i, c in enumerate(text2):\n",
    "            data2[c].append(i)\n",
    "\n",
    "        for i, v1 in enumerate(text1):\n",
    "            for j, v2 in enumerate(text2):\n",
    "                if i ==0:\n",
    "                    if j==0:\n",
    "                        dp[i][j] = 1 if v1==v2 else 0\n",
    "                    else:\n",
    "                        dp[i][j] = 1 if v1==v2  else max(0, dp[i][j-1])\n",
    "                elif j==0:\n",
    "                    dp[i][j] = 1 if v1==v2  else max(0, dp[i-1][j])\n",
    "                else:\n",
    "                    option1 = dp[i][j-1]\n",
    "                    \n",
    "                    # li = data1[v2]\n",
    "                    # largestPos = 0\n",
    "                    # for kk in range(len(li)):\n",
    "                    #     if li[kk]>i:break\n",
    "                    #     largestPos = max(largestPos, li[kk])\n",
    "\n",
    "                    # option2 = None\n",
    "                    # if largestPos==0: option2 = 0\n",
    "                    # else:\n",
    "                    #     option2 = dp[largestPos-1][j-1] +1\n",
    "                    option2 = dp[i-1][j-1] + ( 1 if v1==v2 else 0 )\n",
    "                    option3 = dp[i-1][j]\n",
    "                    \n",
    "                    dp[i][j] = max(option1, option2,option3)\n",
    "                \n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        index = [[[]for i in range(len(text2)+1)]for i in range(len(text1)+1)]\n",
    "        index[len(text1)][len(text2)] = 0\n",
    "        for i in range(len(text1)):\n",
    "            index[i][len(text2)] = 0\n",
    "        for i in range(len(text2)):\n",
    "            index[len(text1)][i] = 0\n",
    "        for i in range(len(text1)-1,-1,-1):\n",
    "            for j in range(len(text2)-1,-1,-1):\n",
    "                l1 = index[i][j+1]\n",
    "                l2 = index[i+1][j]\n",
    "                l3 = 0\n",
    "                if text1[i] == text2[j]:\n",
    "                    l3 = 1 + index[i+1][j+1]\n",
    "                index[i][j] = self.max_value(l1, l2, l3)\n",
    "        return index[0][0]\n",
    "\n",
    "    def max_value(self, l1, l2, l3):\n",
    "        max = l1\n",
    "        for i in (l2, l3):\n",
    "            if i > max:\n",
    "                max = i\n",
    "        return max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        dp=[]\n",
    "        for x in range(len(text1)+1):\n",
    "            temp=[]\n",
    "            for y in range(len(text2)+1):\n",
    "                temp.append([0,-1])\n",
    "            dp.append(temp)\n",
    "        for x in range(1,len(text1)+1):\n",
    "            for y in range(1,len(text2)+1):\n",
    "                if text1[x-1]==text2[y-1]:\n",
    "                    dp[x][y][0],dp[x][y][1] = dp[x-1][y-1][0] + 1,0\n",
    "                else:\n",
    "                    if dp[x-1][y][0]>dp[x][y-1][0]:\n",
    "                        dp[x][y][0],dp[x][y][1]= dp[x-1][y][0],1 \n",
    "                    else:\n",
    "                        dp[x][y][0],dp[x][y][1]= dp[x][y-1][0],2 \n",
    "        res=''\n",
    "        while x>0 and y>0:\n",
    "            temp=dp[x][y][1]\n",
    "            if text1[x-1]==text2[y-1]:\n",
    "                res+=text1[x-1]\n",
    "            if temp==0:\n",
    "                x-=1\n",
    "                y-=1\n",
    "            elif temp==1:\n",
    "                x-=1\n",
    "            elif temp==2:\n",
    "                y-=1\n",
    "        print(res[::-1])\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        text1, text2 = list(text1), list(text2)\n",
    "        n, m = len(text1), len(text2)\n",
    "        dp = [[[0, \"\"] for _ in range(m+1)] for _ in range(n+1)]\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[i][j][0] = dp[i-1][j-1][0] + 1\n",
    "                    dp[i][j][1] = dp[i-1][j-1][1] + text1[i-1]\n",
    "                else:\n",
    "                    if dp[i][j][0] < dp[i-1][j][0]:\n",
    "                        dp[i][j][0] = dp[i-1][j][0]\n",
    "                        dp[i][j][1] = dp[i-1][j][1]\n",
    "                    if dp[i][j][0] < dp[i][j-1][0]:\n",
    "                        dp[i][j][0] = dp[i][j-1][0]\n",
    "                        dp[i][j][1] = dp[i][j-1][1]\n",
    "                    if dp[i][j][0] < dp[i-1][j-1][0]:\n",
    "                        dp[i][j][0] = dp[i-1][j-1][0]\n",
    "                        dp[i][j][1] = dp[i-1][j-1][1]\n",
    "\n",
    "        \n",
    "        return dp[-1][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        hashmap = dict()\n",
    "        def dfs(i, j):\n",
    "            if i == 0 and j == 0:\n",
    "                if text1[i] == text2[j]:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            elif i == 0 and j > 0:\n",
    "                if text1[i] in text2[:j+1]:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0 \n",
    "            elif i > 0 and j == 0:\n",
    "                if text2[j] in text1[:i+1]:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0 \n",
    "            a = str(i) + '+' + str(j)\n",
    "            if a in hashmap:\n",
    "                return hashmap[a]\n",
    "             \n",
    "            if text1[i] == text2[j]:\n",
    "                b = dfs(i - 1, j - 1) + 1\n",
    "                hashmap[a] = b\n",
    "                return b\n",
    "            else:\n",
    "                b = max(dfs(i - 1, j), dfs(i, j - 1))\n",
    "                hashmap[a] = b\n",
    "                return b\n",
    "        return dfs(len(text1) - 1, len(text2) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        text1_len, text2_len = len(text1), len(text2)\n",
    "        # text1, text2, min_len = (text1, text2, text1_len) if text1_len < text2_len else (text2, text1, text2_len)\n",
    "        pb = {}\n",
    "        total = 0\n",
    "        for i in range(len(text1)):\n",
    "            for j in range(len(text2)):\n",
    "                if text1[i] == text2[j]:\n",
    "                    total = pb.get(f'{i-1}_{j-1}', 0) + 1\n",
    "                else:\n",
    "                    total = max(pb.get(f'{i - 1}_{j}', 0), pb.get(f'{i}_{j - 1}',0))\n",
    "                pb.update({f'{i}_{j}': total})\n",
    "        return total\n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        # dp[i][j]定位为 text1[:i] text2[：j]的最长公共子序列的长度\n",
    "\n",
    "        m = len(text1)\n",
    "        n = len(text2)\n",
    "\n",
    "        memo = dict()\n",
    "\n",
    "        # 递推关系 如果 i==j dp[i][j] = dp[i-1][j-1] + 1\n",
    "        # 如果 i!=j dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])\n",
    "        dp = [[0 for _ in range(n+1)]for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if str(i)+'+'+str(j) in memo.keys():\n",
    "                    dp[i][j] = memo[str(i)+'+'+str(j)]\n",
    "                elif text1[i-1] == text2[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1] + 1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "                memo[str(i)+'+'+str(j)] = dp[i][j]\n",
    "        return dp[-1][-1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "  dcache = {}\n",
    "  def dfs(self, s1, s2, i1, i2):\n",
    "    if i1 == -1 or i2 == -1:\n",
    "      return 0\n",
    "    else:\n",
    "      if (i1, i2) in self.dcache:\n",
    "        return self.dcache[(i1, i2)]\n",
    "      if s1[i1] == s2[i2]:\n",
    "        print(i1, i2)\n",
    "        temp = self.dfs(s1, s2, i1-1, i2-1) + 1\n",
    "        self.dcache[(i1, i2)] = temp\n",
    "        return temp\n",
    "      else:\n",
    "        # print(i1, i2)\n",
    "        temp = max(self.dfs(s1, s2, i1-1, i2), self.dfs(s1, s2, i1, i2-1))\n",
    "        self.dcache[(i1, i2)] = temp\n",
    "        return temp\n",
    "\n",
    "  def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "    self.dcache.clear()\n",
    "    return self.dfs(text1, text2, len(text1)-1, len(text2)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        #1、深度优先搜索，从上到下走到树的最深处，枚举所有结果，对于树，选择递归方式\n",
    "        # def dfs(i,j): #定义递归函数\n",
    "        #     if i == -1 or j == -1:return 0\n",
    "        #     if text1[i] == text2[j]: #从最后位置进行判断，符合要求则往前一个位置，另外符合要求的那个需要加上去，也就是+1\n",
    "        #         return dfs(i-1,j-1) + 1\n",
    "        #     else:\n",
    "        #         return max(dfs(i-1,j),dfs(i,j-1)) #否则，从i和j分别向上移动的结果中取最大值\n",
    "        # return dfs(len(text1)-1,len(text2)-1) #调用递归函数\n",
    "        \n",
    "        #2、记忆化搜索，在dfs基础上对已经走过的路进行储存，减少重复计算\n",
    "        memo = {} #存结果用\n",
    "        def memoization(i,j):\n",
    "            if (i,j) in memo:return memo[(i,j)]\n",
    "            if i ==-1 or j == -1:return 0\n",
    "            if text1[i] == text2[j]:\n",
    "                result = memoization(i-1,j-1) + 1\n",
    "            else:\n",
    "                result = max(memoization(i-1,j),memoization(i,j-1))\n",
    "            memo[(i,j)] = result\n",
    "            return result\n",
    "        return memoization(len(text1)-1,len(text2)-1)\n",
    "\n",
    "\n",
    "        # m, n = len(text1), len(text2)\n",
    "        # dp = [[0]*(n+1) for _ in range(m+1)] #创建(m+1,n+1)的矩阵\n",
    "        # for i in range(1,m+1):\n",
    "        #     for j in range(1,n+1):\n",
    "        #         if text1[i-1] == text2[j-1]: #这里的i和j不是索引，而是前i/j个元素的结果\n",
    "        #             dp[i][j] = dp[i-1][j-1] +1\n",
    "        #         else:\n",
    "        #             dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n",
    "        # return dp[m][n]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
